Color in documents is the result of a combination of a limited set of colors over a small area, in densities selected to integrate to a desired color response. This is accomplished in many printing devices by reproducing separations of the image, where each separation provides varying density of a single primary color. When combined together with other separations, the result is a full color image.
In the digital reproduction of documents, a separation is conveniently represented as a monochromatic bitmap, which may be described as an electronic image with discrete signals (hereinafter, pixels) defined by position and density. In such a system, density is described as one level in a number of possible states or levels. When more than two levels of density are used in the description of the image, the levels are often termed "gray", indicating that they vary between a maximum and minimum, and without reference to their actual color. Most printing systems have the ability to reproduce an image with a small number of levels, most commonly two, although other numbers are possible. Common input devices including document scanners, digital cameras and the computer imagery generators, however, are capable of describing an image with a substantially larger number of gray levels, with 256 levels a commonly selected number, although larger and smaller levels are possible. It is required that an image initially described at a large set of levels also be describable at a smaller set of levels, in a manner which captures the intent of the user. In digital reproduction of color documents this means that each of the color separations is reduced from the input number of levels to a smaller output number of levels. The multiple color separations are combined together at printing to yield the final color print. Commonly, color documents are formed using cyan, magenta and yellow colorants or cyan, magenta, yellow and black colorants. A larger number or alternative colorants may also be used.
In printing documents,, the desired density of color over an area is commonly achieved by halftoning, where separation density variation is represented by placing greater or less numbers of ON pixels in a discrete area of a separation. In one halftoning method known as dithering or screening, over a given area having a number of gray separation pixels therein, a value representing the density of each separation pixel of an array of gray separation pixels within the area is compared to one of a set of preselected thresholds (the thresholds are stored as a dither matrix and the repetitive pattern generated by this matrix is considered a halftone cell) as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the dither matrix will be exceeded, i.e. the image value at that specific location is larger than the value stored in the dither matrix for that same location, while others are not. In the binary case, the separation pixels or cell elements for which the thresholds are exceeded might be printed as a maximum colorant value, while the remaining separation pixels are allowed to remain white, dependent on the actual physical quantity described by the data. The described halftoning method produces an output pattern that is periodic or quasi-periodic in the spatial coordinates.
Error diffusion is another halftoning method and is taught in "An Adaptive Algorithm for Spatial Greyscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976) (hereinafter, "Floyd and Steinberg"). Another, more elaborate method would be the error diffusion techniques of U.S. Pat. No. 5,045,952 to Eschbach, which serves to provide image dependent edge enhancement, assigned to the same assignee as the present invention. Error diffusion attempts to maintain gray by making the conversion from gray pixels to binary or other level pixels on a pixel-by-pixel basis. The procedure examines each pixel with respect to a threshold, and the difference between the gray level pixel value and the output value is forwarded to a selected group or set of neighboring pixels, in accordance with a weighting scheme. The output binary pattern of the error diffusion algorithm and its derivatives is a pattern with a local periodicity related to the input density level, but with no global periodicity, see "Analytic Description of the 1-D Error Diffusion Technique for Halftoning," Optics Communications, Vol. 52, No. 3, 165-168 (1984) by R. Eschbach and R. Hauck.
Other error diffusion methods include, "On the Error Diffusion Technique for Electronic Halftoning" by Billotet-Hoffmann and Bryngdahl, Proceedings of the SID, Vol. 24/3, (1983), pp. 253-258; and U.S. Pat. No. 5,226,094 to Eschbach. A technique related to error diffusion is taught in the MAE (Minimum Average Error) method of error diffusion described in "Images from Computers", by M. Schroeder, IEEE Spectrum, March 1969, pp. 66-78, in which an error correction is performed that only affects a local neighborhood. This method does not preserve the gray density. One particularly effective error diffusion variant is taught in co-pending U.S. patent application Ser. No. 08/167,758, filed Dec. 15, 1993, entitled "Method for Quantization Gray Level Pixel Data with Extended Distribution Set", by J. Shiau and Z. Fan, U.S. Pat. No. 5,353,127.
Dithering creates problems in color document reproduction where the repeating pattern of a screen through the image, when superposed over similar repeating patterns in multiple separations, can cause moire or other artifacts, particularly in printing systems with less than ideal registration between separations. U.S. Pat. No. 4,149,194 to Holladay. addresses this problem to some extent by providing rotated screens which tend to reduce, although not eliminate moire.
Error diffusion, because it operates on a pixel-by-pixel basis is non-periodic, which mitigates the problems of moire. However, since error diffusion is a deterministic process, misregistration of the different deterministic color separations can lead to a color shift. This color shift can be reduced by introducing a random element into the error diffusion process, but at the expense of image noise.
All of the references cited herein are incorporated by reference for their teachings.